package Ch_1_5_Case_Study_Union_Find;

public class Practise_1_5_09 {
	public static void main(String[] args) {
		/*
		 * 作出树状森林图后开始分析
		 * 
		 * 我们的连接方式都是从某个结点向上追溯直到根结点
		 * 然后将小树根结点连接到大树根结点上，树的大小判断不是根据高度，
		 * 而是根据树包含的结点个数
		 * 
		 * 如果 0 -> 1, 此时 1 规模为 2
		 * 由图可知，要完成 3 为根结点子树的连接，必须按如下步骤
		 * 
		 * 1， 7 -> 3
		 * 2， 2 -> 3
		 * 3， 3 -> 1 
		 * 
		 * 在第三步中，由于 3为根结点子树规模为 3, 而此时 1为根结点
		 * 子树规模为 2, 不可能出现大子树连接到小子树的情况
		 * 
		 * 现在已经可以得出该连接不会出现在加权的 QuickUnion 算法中，
		 * 只可能出现在 QuickUnion 中
		 * 
		 * 再分析另一侧
		 * 要完成以 5为根结点子树的连接，必须按如下步骤
		 * 
		 * 1，8 -> 4
		 * 2，9 -> 5 (1，2两步顺序可以互调)
		 * 3，4 -> 5
		 * 
		 * 所以 5为根结点子树这个局部是可能出现的
		 * 
		 * 现在考虑以 6为根结点子树的连接，必须按如下步骤
		 * 
		 * 1，5 -> 6
		 * 2，9 -> 5 (不可能出现)
		 * 
		 * 1，5 -> 6
		 * 2，4 -> 5 (不可能出现)
		 * 
		 * 所以 6为根结点的子树是不可能出现的
		 * 
		 * 综上所述，该连接的诸多子部分不可能出现，因此这个整体连接不可能出现
		 * 
		 */
	}
}
